package data_structures_and_algorithms.recursion_traceback;


import java.util.*;

/**
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [1,1,2]
 * 输出：
 * [[1,1,2],
 *  [1,2,1],
 *  [2,1,1]]
 * 示例 2：
 *
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 *  
 *
 * 提示：
 *
 * 1 <= nums.length <= 8
 * -10 <= nums[i] <= 10
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/permutations-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 *
 // 解法一：调用第一种解法
 //        return permuteUniqueOld(nums);


 // 解法二：先排序，然后省去空间开销的做法
 然后交换时候判断 相邻元素相等直接跳过
 */
public class _0047_permuteUnique_exist_repeat_num {

    public static void main(String[] args) {
        int[] nums = new int[]{1,1,2,2};
        List<List<Integer>> lists = new _0047_permuteUnique_exist_repeat_num().permuteUnique(nums);
        System.out.println(Arrays.toString(lists.toArray()));
    }
    public List<List<Integer>> permuteUnique(int[] nums) {
        // 解法一：调用第一种解法
//        return permuteUniqueOld(nums);


        // 解法二：先排序，然后省去空间开销的做法
        Arrays.sort(nums);

        return permuteUniqueSort(nums);

    }

    List<List<Integer>> list = new LinkedList<>();
    public List<List<Integer>> permuteUniqueOld(int[] nums) {
        backtraceHelper(nums, 0);

        return list;
    }

    public void backtraceHelper(int[] nums, int index){
        if (index == nums.length - 1){
            list.add(buildListFromArray(nums));
            return;
        }

        Set<Integer> visited = new HashSet<>();
        for (int i = index; i < nums.length; i++) {
            if (visited.contains(nums[i])){
                continue;
            }
            visited.add(nums[i]);
            swap(nums, index, i);
            backtraceHelper(nums, index + 1);
            swap(nums, index, i);
        }

    }

    public List<List<Integer>> permuteUniqueSort(int[] nums) {
        backtraceHelper(nums, 0);

        return list;
    }

    public void backtraceSort(int[] nums, int index){
        if (index == nums.length - 1){
            list.add(buildListFromArray(nums));
            return;
        }

        for (int i = index; i < nums.length; i++) {
            if (i > index && nums[i] == nums[i - 1]){
                continue;
            }
            swap(nums, index, i);
            backtraceHelper(nums, index + 1);
            swap(nums, index, i);
        }
    }

    private void swap(int[] nums, int index, int i) {
        int temp = nums[index];
        nums[index] = nums[i];
        nums[i] = temp;
    }

    private List<Integer> buildListFromArray(int[] nums) {
        List<Integer> arrayList = new ArrayList<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            arrayList.add(nums[i]);
        }
        return arrayList;
    }
}
